<?php
/**
 * @title 5466. 最多的不重叠子字符串 - 穷列+剪枝
 * @author start2004
 */

class Solution {

    /**
     * @param String $s
     * @return String[]
     */
    function maxNumOfSubstrings($s) {
        /**
         * @since 2020-07-19 记录每个字符起始位置
         */
        $charArray = [];

        /**
         * @since 2020-07-19 迭代, 获取位置
         */
        for($i=0, $len=strlen($s); $i<$len; $i++){
            $char = $s[$i];

            /**
             * @since 2020-07-23 存在只更新终点
             */
            if(isset($charArray[$char])){
                $charArray[$char][1] = $i;
            } else {
                $charArray[$char] = [$i, $i];
            }
        }
        // return $charArray;

        /**
         * @since 2020-07-23 子字符串集合, 做了部分剪枝
         */
        $strArray = [];

        /**
         * @since 2020-07-23 遍历字符串, 查找子字符串
         */
        for($i=0; $i<$len; $i++){
            /**
             * @since 2020-07-23 第一个字符暂时定右边界 `→|`
             */
            $right = $charArray[$s[$i]][1];

            /**
             * @since 2020-07-23 判断这区间内字符, 是否需要延长右边界
             */
            for($j=$i; $j<=$right; $j++){
                $c = $s[$j];

                /**
                 * @since 2020-07-23 该字符左边界 `|←` 越界, 以`i`起点的子字符串不存在
                 */
                if($charArray[$c][0] < $i){
                    $right = false;
                    break;
                } else {}
                $right = max($right, $charArray[$c][1]);
            }

            /**
             * @since 2020-07-23 子字符串搜索完毕
             */
            if($right !== false){
                $strArray[] = [$i, $right, substr($s, $i, $right-$i+1)];
            } else {}
        }
        // return $strArray;

        /**
         * @since 2020-07-23 相互不重叠字符串集合
         */
        $result = [];

        /**
         * @since 2020-07-23 最短不重叠
         */
        $strlen = count($strArray);
        for($i=0, $iMax=$strlen-2; $i<=$iMax; $i++){
            $right = $strArray[$i][1];
            $nextLeft = $strArray[$i+1][0];

            /**
             * @since 2020-07-23 需要和下个节点错开
             */
            if($right<$nextLeft){
                $result[] = $strArray[$i][2];
            } else {}
        }

        /**
         * @since 2020-07-23 收官
         */
        $result[] = $strArray[$strlen-1][2];

        /**
         * @return
         */
        return $result;
    }
}




/**
 * @url http://127.0.0.1/leetcode/202007/2020.07.23_4.php
 */
$datas = [
    "adefaddaccc",
    "abbaccd",
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->maxNumOfSubstrings($data);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
